This application claims priority to an application entitled xe2x80x9cTurbo Interleaving Apparatus and Methodxe2x80x9d filed in the Korean Industrial Property Office on May 19, 1999 and assigned Serial No. 99-18928 and an application filed in the Korean Industrial Property Office on May 21, 1999 and assigned Serial No. 99-18560, the contents of which are hereby incorporated by reference.
1. Field of the Invention
The present invention relates generally to a turbo encoder used for radio communication systems (including satellite, ISDN, digital cellular, W-CDMA, and IMT-2000 systems), and in particular, to an internal interleaver of a turbo encoder.
2. Description of the Related Art
In general, an interleaver used for a turbo encoder randomizes an address of input information word and improves a distance property of a codeword. In particular, it has been decided that a turbo code will be used in a supplemental channel (or data transmission channel) of IMT-2000 (or CDMA-2000) and IS-95C air interfaces and in a data channel of UMTS (Universal Mobile Telecommunication System) proposed by ETSI (European Telecommunication Standards Institute). Thus, a method for embodying an interleaver for this purpose is required. In addition, the invention relates to an error correction code which greatly affects performance improvement of the existing and future digital communication systems.
For an existing internal interleaver for a turbo encoder (hereinafter, referred to as a turbo interleaver), there have been proposed various interleavers such as PN (Pseudo Noise) random interleaver, random interleaver, block interleaver, non-linear interleaver, and S-random interleaver. However, so far, such interleavers are mere algorithms designed to improve their performances in terms of scientific researches rather than implementation. Therefore, when implementing an actual system, the hardware implementation complexity must be taken into consideration. A description will now be made of properties and problems associated with the conventional interleaver for the turbo encoder.
Performance of the turbo encoder is dependent upon its internal interleaver. In general, an increase in the input frame size (i.e., the number of information bits included in one frame) enhances the effectiveness of the turbo encoder. However, an increase in interleaver size causes a geometric increase in calculations. Therefore, in general, it is not possible to implement the interleaver for the large frame size.
Therefore, in general, the interleavers are implemented by determining conditions satisfying several given criteria. The criteria are as follows:
Distance Property: The distance between adjacent codeword symbols should be maintained to a certain extent. This has the same function as a codeword distance property of the convolutional code, and as a criterion indicating this, a minimum free distance is used which is a value of a codeword path or a codeword sequence with the minimum Hamming weight out of the code symbol sequences (or codeword paths) output on the trellis. In general, it is preferable that the interleaver should be designed to have the longer free distance, if possible.
Random Property: A correlation factor between output word symbols after interleaving should be much lower than a correlation factor between original input word symbols before interleaving. That is, randomization between the output word symbols should be completely performed. This makes a direct effect on the quality of extrinsic information generated in continuous decoding.
Although the above criteria are applicable to a general turbo interleaver, it is difficult to clearly analyze the properties when the interleaver increases in size.
In addition, another problem occurring when designing the turbo interleaver is that the minimum free distance of the turbo code varies according to the type of the input codeword. That is, when the input information word has a specific sequence pattern defined as a critical information sequence pattern (CISP), the free distance of the output code symbols generated from the turbo encoder has a very small value. If the input information word has a Hamming weight 2, the CISP occurs when the input information word has two information bits of xe2x80x981xe2x80x99 and can also occur when the input information word has 3 or more information bits of xe2x80x981xe2x80x99. However, in most cases, when the input information word has 2 information bits of xe2x80x981xe2x80x99, the minimum free distance is formed and most error events occur in this condition. Therefore, when designing the turbo interleaver, an analysis is generally made on the case where the input information word has the Hamming weight 2. A reason that the CISP exists is because the turbo encoder generally uses RSC (Recursive Systematic Convolutional Codes) encoders for the component encoders shown in FIG. 1 (described further below). To improve performance of the turbo encoder, a primitive polynomial should be used for a feedback polynomial (gf(x) of FIG. 1) out of the generator polynomials for the component encoder. Therefore, when the number of the memories of the RSC encoder is m, a feedback sequence generated by the feedback polynomial continuously repeats the same pattern at a period of 2mxe2x88x921. Therefore, if an input information word xe2x80x981xe2x80x99 is received at the instance corresponding to this period, the same information bits are exclusive-ORed, so that the state of the RSC encoder becomes an all-zero state henceforth, thus generating the output symbols of all 0""s. This means that the Hamming weight of the codeword generated by the RSC encoder has a constant value after this event. That is, the free distance of the turbo code is maintained after this time, and the CISP becomes a main cause of a reduction in the free distance of the turbo encoder, whereas, as noted above, a larger free distance is desirable.
In this case (in the prior art of turbo interleaver), to increase the free distance, the turbo interleaver randomly disperses the CISP input information word so as to prevent a decrease in the free distance at the output symbol of the other component RSC encoder.
The above-stated properties are fundamental features of the known turbo interleaver. However, for the CISP, it is conventional that the information word has the minimum Hamming weight, when the input information word has the Hamming weight 2. In other words, the fact that the CISP can be generated even when the input information word has the Hamming weight 1 (i.e., when the input information word has one information bit of xe2x80x981xe2x80x99) was overlooked, when the information word input to the turbo encoder had the type of a block comprised of frames.
For example, a prime interleaver (PIL) designated as the working model of the turbo code interleaver specified by the present UMTS standard exhibits such problems, thus having a degraded free distance property. That is, the implementation algorithm of the model PIL turbo interleaver include 3 stages, of which the second stage, which plays the most important role, performs random permutation on the information bits of the respective groups. The second stage is divided into three cases of Case A, Case B and Case C, and the Case B always involves the case where the free distance is decreased due to the event where the input information word has the Hamming weight 1. In addition, even the Case C involves a possibility that such an event will occur. The detailed problems will be described later with reference to the PIL.
In conclusion, when various interleaver sizes are required and the hardware implementation complexity is limited in the IMT-2000 or UMTS system, the turbo interleaver should be designed to guarantee the optimal interleaver performance by taking the limitations into consideration. That is, the required interleaver should be able to guarantee uniform performance for the various interleaver sizes, while satisfying the above-stated properties. More recently, there have been proposed several types of the interleavers for a PCCC (Parallel Concatenated Convolutional Codes) turbo interleaver, and a LCS (Linear Congruential Sequence) turbo interleaver has been provisionally decided as the turbo interleaver in the IMT-2000 (or CDMA-2000) and IS-95C specifications. However, most of these turbo interleavers have the problems of the CSIP with Hamming weight 1, and the details of implementing these turbo interleavers are still not defined. Therefore, the present invention proposes a solution of the turbo interleaver""s problems, and a new method for implementing the turbo interleaver. In addition, the invention shows the PIL interleaver which is a working assumption of the UMTS turbo interleaver, and proposes a solution of this interleaver""s problem.
To sum up, the prior art has the following disadvantages.
(1) The turbo interleaver is designed for the infinite frame size on the basis of the CISP for which the input information word has the Hamming weight 2, without considering the fact that determining the CISP according to the type of the input information word is limited to the frame size. However, in an actual system, the frame has a finite size, thus causing a decrease in the free distance of the turbo code.
(2) In designing the existing turbo interleaver, the fact that the input information word may have Hamming weight 1 was not considered. In other words, for the finite frame size, the turbo interleaver design rule should be determined in consideration of the fact that the minimum free distance generated in the PCCC turbo encoder is determined by the CISP having the Hamming weight 1. However, this was not fully considered for the existing turbo interleavers.
(3) The Prime interleaver (PIL) designated as the working assumption of the turbo code interleaver defined by the UMTS specification involves such problems, thus having degraded free distance performance.
It is, therefore, an object of the present invention to provide an interleaving device and method for analyzing properties of a turbo interleaver and a property of a critical information sequence pattern (CISP) to improve performance of the turbo interleaver.
It is another object of the present invention to provide an interleaving device and method for improving free distance performance of a turbo code for the case where an input information word has a Hamming weight 1 when the information word input to a turbo interleaver has a block type comprised of frames.
It is a further object of the present invention to provide an interleaving device and method for solving the problem that the free distance is decreased when an input information word has a Hamming weight 1 in a prime interleaver (PIL) that is the turbo interleaver specified in the UMTS specification.
To achieve the above objects, there is provided a 2-dimensional interleaving method comprising dividing a frame of input information bits into a plurality of groups and sequentially storing the divided groups in a memory; permuting the information bits of the groups according to a given rule and shifting an information bit existing at the last position of the last group to a position preceding the last position; and selecting the groups according to a predetermined order, and selecting one of the information bits in the selected group.